package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //黄金矿工
        class Solution {
            boolean[][] vis;
            int m,n;
            int[] dx = {1,-1,0,0};
            int[] dy = {0,0,1,-1};

            public int getMaximumGold(int[][] grid) {
                m = grid.length;
                n = grid[0].length;
                vis = new boolean[m][n];
                int ret = 0;

                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        if(grid[i][j] != 0){              // 任意非零格都可作为起点
                            vis[i][j] = true;
                            int cur = dfs(grid, i, j);    // 从该点出发的最大收益
                            vis[i][j] = false;
                            ret = Math.max(ret, cur);
                        }
                    }
                }
                return ret;
            }

            public int dfs(int[][] grid, int si, int sj){
                int bestNext = 0;                         // 记录四邻的最佳后续收益
                for(int k = 0; k < 4; k++){
                    int x = si + dx[k], y = sj + dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y] != 0){
                        vis[x][y] = true;
                        int gain = dfs(grid, x, y);      // 接住子递归返回值
                        vis[x][y] = false;
                        if(gain > bestNext) bestNext = gain;
                    }
                }
                return grid[si][sj] + bestNext;           // 当前格金子 + 最佳后续
            }
        }


        //不同路径III
        class Solution2 {
            boolean[][] vis;
            int m,n;
            int[] dx = {1,-1,0,0};
            int[] dy = {0,0,1,-1};
            int step; // 空格(0) 的数量
            int ret;  // 路径计数

            public int uniquePathsIII(int[][] grid) {
                // 防御性初始化
                step = 0;
                ret  = 0;

                m = grid.length;
                n = grid[0].length;
                vis = new boolean[m][n];

                // 统计所有 0 的数量
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        if(grid[i][j] == 0) step++;
                    }
                }

                // 从起点 1 出发
                for(int i = 0; i < m; i++){
                    for(int j = 0; j < n; j++){
                        if(grid[i][j] == 1) {
                            vis[i][j] = true;           // 起点先标记
                            dfs(grid, i, j, 0);         // 已走 0 步
                            vis[i][j] = false;          // 回溯恢复
                        }
                    }
                }
                return ret;
            }

            public void dfs(int[][] g, int si, int sj, int count){
                // 到达终点：判断是否覆盖所有非障碍格（0 与 1 与 2）
                if(g[si][sj] == 2){
                    int need = step + 1;                // 从 1 到 2 共需走的步数
                    if(count == need) ret++;            // 覆盖完才计数
                    return;                             // 终点必须停止
                }

                for(int k = 0; k < 4; k++){
                    int x = si + dx[k], y = sj + dy[k];
                    if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && g[x][y] != -1){
                        vis[x][y] = true;
                        dfs(g, x, y, count + 1);
                        vis[x][y] = false;
                    }
                }
            }
        }

    }
}